/*
 * @lc app=leetcode.cn id=911 lang=cpp
 *
 * [911] 在线选举
 */

// @lc code=start
class TopVotedCandidate
{
public:
    // 记录在某一时刻的票王
    vector<int> vec;
    TopVotedCandidate(vector<int> &persons, vector<int> &times)
    {
        vec.assign(times[times.size() - 1] + 1, -1);
        // 记录persons得票数
        vector<int> res(persons.size(), 0);
        // 记录上一次的票王
        int before = 0;
        for (int i = 0; i < times.size(); i++)
        {
            // 比较当次被投票人和上一次的大小
            if (res[before] <= ++res[persons[i]])
                before = persons[i];
            vec[times[i]] = before;
        }
        // 对于并未出现在times中的时刻赋前一刻的值,使q()时,O(1)调用
        for (int i = 0; i < vec.size(); i++)
        {
            if (vec[i] == -1 && i != 0)
                vec[i] = vec[i - 1];
        }
    }

    int q(int t)
    {
        return t >= vec.size() ? vec[vec.size() - 1] : vec[t];
    }
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */
// @lc code=end

